package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/7 16:07
 * https://leetcode-cn.com/problems/top-k-frequent-words/
 */
public class Title692 {

    public static List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> hash = new HashMap<>();
        for (String s : words) {
            hash.put(s, hash.getOrDefault(s, 0) + 1);
        }
        Set<Map.Entry<String, Integer>> strings = hash.entrySet();
        PriorityQueue<Map.Entry<String, Integer>> priorityQueue = new PriorityQueue<>((a, b) -> {
            //key降序 //字典降序Z 。。。。A
            if (a.getValue().equals(b.getValue())) {
                return b.getKey().compareTo(a.getKey());
            }
            //value升序
            return a.getValue().compareTo(b.getValue());
        });
        for (Map.Entry<String, Integer> entry : strings) {
            priorityQueue.offer(entry);
            // Z A 频率相同，弹出Z； 频率不同，弹出频率小的
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }
        //Z Y Y  A A
        List<String> result = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            ((LinkedList<String>) result).offerFirst(priorityQueue.poll().getKey());
        }
        return result;
    }

    public static void main(String[] args) {
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        topKFrequent(words, 2);
    }
}
